/// @tags: Graph Tree
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

using std::cin, std::cout, std::endl;

namespace BlueQuantum {

constexpr int maxn = 2e5 + 5;

int n, m;
int ecnt;
int heads[maxn];

struct Edge {
  int v, nxt, col;
} e[maxn * 2];

inline void add(int u, int v) {
  e[++ecnt].v = v, e[ecnt].nxt = heads[u], e[ecnt].col = 0, heads[u] = ecnt;
}

bool vis[maxn];
std::vector<int> B;
int deg[maxn], f[maxn], dep[maxn];

void dfs(int u, int fa) {
  vis[u] = true;
  f[u] = fa;
  dep[u] = dep[fa] + 1;
  for (int i = heads[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (vis[v]) {
      if (v != fa) B.push_back(v), deg[e[i].v]++;
      continue;
    }
    e[i].col = e[i ^ 1].col = 1;
    dfs(v, u);
  }
}

void solve() {
  // exclude two-element circle
  if (B.size() < 6) return;
  for (auto it : B)
    if (deg[it] < 2) return;
  std::vector<int> vec;
  for (auto it : B) vec.push_back(it);
  std::sort(vec.begin(), vec.end(), [&](const int lhs, const int rhs) -> bool {
    return dep[lhs] > dep[rhs];
  });
  int u = vec[0];
  int x, y;
  for (int i = heads[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (e[i].col == 0) x = i;
    if (v == f[u]) y = i;
  }
  e[x].col = e[x ^ 1].col = 1;
  e[y].col = e[y ^ 1].col = 0;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    ecnt = 1;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
      heads[i] = f[i] = dep[i] = deg[i] = 0, vis[i] = false;
    B.clear();
    for (int i = 1; i <= m; ++i) {
      int x, y;
      cin >> x >> y;
      add(x, y), add(y, x);
    }
    dfs(1, 0);
    solve();
    for (int i = 2; i <= 2 * m; i += 2) cout << e[i].col;
    cout << endl;
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("CF1726D Edge Split.in", "r", stdin);
  freopen("CF1726D Edge Split.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
